By

文章目录
  1. 1. 题目
  2. 2. 思路
  3. 3. 代码

本系列代码见我的Leetcode仓库

题目

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

这个题在很多OJ上都有，难度归类为简单，是图形字符串操作。即给一个字符串，是按照7415963（看小键盘）的方式书写的，书写时候只要指定了行数，那么他的结构就固定了。题目要求将固定了之后的结果按横向读取顺序来输出。

思路

其实只需要计算每个字符相应的位置就行了，思路如下：

逐行计算，根据每行字符位置的计算公式。共扫描n趟。

首先有些字符的位置是能确定的，就是第一行和最后一行的字符。

当行数n确定之后，第一行每个字附间的间隔距离就是2n-2，也就是每逢第2k-2个的字符就在第一行中，最后一行同理。

其中间的就比较麻烦，每一个ZigZag循环节每一行都至多只有三个字符。观察同一行中的某字符发现，奇偶列分别具有各自的规律，例如4跟5相距下三角，5跟6相距上三角，这种情况他的位置就是前一个字符位置+下半部分的三角，另一种情况就是前一个字符位置+上半部分的三角，于是咱们可以通过第一个字符的位置跟当前是奇数还是偶数列来计算这一行所有字符的位置。

公式：第i行,第k个字符(从0计)

if k is odd
index = index + 2 * (n -i -1)
else
index = index + 2 * i

至此全部字符的位置计算完毕。

需要注意三个细节，1当然是判空，2是下标合法性检查，因为到结尾的时候凑不够一个完整的ZigZag，3是当行数大于字符串长度时退化为一个列，此时公式不再起作用，所以2和3都需要在条件中加入下标/行数<字符串长度的限制

代码

Language:java

public class Solution {
   public String convert(String s, int nRows) {
       if (nRows <= 1 || s.length() == 0)
            return s;


         String res = "";
         int len = s.length();
         for (int i = 0; i < len && i < nRows; ++i)
         {
             int indx = i;
             res += s.charAt(indx);

                     for (int k = 1; indx < len; ++k)
             {
                 //第一行或最后一行，使用公式1：
                 if (i == 0 || i == nRows - 1)
                 {
                     indx += 2 * nRows - 2;
                 }
                 //中间行，判断奇偶，使用公式2或3
                 else
                 {
                     if (k%2 !=0)  //奇数位
                         indx += 2 * (nRows - 1 - i);
                     else indx += 2 * i;
                 }

                         //判断indx合法性
                 if (indx < len)
                 {
                     res += s.charAt(indx);
                 }
             }
         }
         return res;
   }
}
文章目录
  1. 1. 题目
  2. 2. 思路
  3. 3. 代码